package leetcode每日一题.leetcode20212;

/**
 * 1. 问题描述
 *      今天，书店老板有一家店打算试营业customers.length分钟。每分钟都有一些顾客（customers[i]）会进入书店，
 *      所有这些顾客都会在那一分钟结束后离开。
 *      在某些时候，书店老板会生气。如果书店老板在第i分钟生气，那么 grumpy[i]=1，否则 grumpy[i] = 0。当书店老板生气时，
 *      那一分钟的顾客就会不满意，不生气则他们是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续X分钟不生
 *      气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
 *
 * 2. 算法分析
 *      分析题目含义：
 *          customers数组的含义：customers[i]表示第i分钟有多少顾客来到书店
 *          grumpy数组的含义：grumpy[i]表示第i分钟书店老板是否生气 grumpy[i] = 0表示没有生气 grumpy[i] = 1 表示生气
 *          X的含义：表示连续X分钟内不生气
 *          我们的目的是求出老板一天可以使得多少顾客满意的最大人数
 *          对于这个问题，我们可以从两个角度来分析，如果老板不发动技能的前提下，我们找到老板可以使得顾客满意的最大人数
 *          对于此，实际上通过一次扫描就可以找到，将grumpy[i]=0对应的customers[i]相加起来，这就是没有发动技能时可
 *          以使得满意的最大顾客数
 *          对于不发动技能的情况下，实际上上述问题是一个离散的问题，因为可能没有连续是得顾客满意的区间，但是如果一旦发
 *          动技能，X是一个连续的分钟区间，我们通过滑动窗口找到最大顾客满意的X分钟区间，将这个差值加到之前没有发动技能
 *          找到的最大顾客数量，就是老板一天可以使得顾客满意的最大数量
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class Q024_爱生气的书店老板 {
    public int maxSatisfied(int[] customers, int[] grumpy, int X) {
        int sum0 = 0; // 记录老板没有生气的人数
        int compansate = 0; // 记录补差的人数，全局最大的
        int curCompansate = 0; // 记录当前窗口中的补差数
        int n = grumpy.length; // 分钟数
        int left = 0;
        int right = 0;
        while(right < n) {
            // 如果当前right对应的恰好为老板没有生气，直接加到sum0中
            sum0 += (grumpy[right] == 0) ? customers[right] : 0;
            // 如果当前right对应的恰好为老板生气了，发动技能，补差
            curCompansate += (grumpy[right] == 1) ? customers[right] : 0;
            // 当前右窗口判断完毕之后，移动右窗口right
            right++;
            // 移动之后判断当前窗口长度是否大于给定的技能限制X分钟(上述为[left,right),区间长度为right-left，不需要+1)
            if(right - left > X) {
                // 如果长度已经大于给定的限制，需要调整左窗口left，在调整之前我们还是需要判断
                // 当前左窗口对应的状态，如果当前左窗口对应的是老板生气的状态，当前不差需要去掉对应的顾客数量
                curCompansate -= (grumpy[left] == 1) ? customers[left] : 0;
                left++;
            }
            compansate = Math.max(curCompansate,compansate);
        }
        return compansate + sum0;
    }
    
}
